This application relates generally to computer networks, and more particularly, to assigning telecommunications nodes to community of interest clusters (“CICs”).
Telecommunications networks continue to experience steady growth in demand for a broad range of voice, data and broadband services. Not only must telecommunications service providers respond to increases in the overall volume of traffic, but they must also respond to customer requirements for ever-higher bandwidth connections. This has resulted in larger and more complex networks.
As demand grows, network planners and engineers must continually route new end-to-end connections (e.g., circuits) over the network. This goes beyond finding simple “shortest available path” connections. For example, depending on the restoration requirements for these circuits, it may be necessary to provision capacity over two disjoint paths (to provide “1+1 diversity” for the circuit), or to design and provision the circuit within a Synchronous Optical Networking (“SONET”) self-healing ring structure, etc.
As telecommunications networks continue to grow in size and complexity, the need for efficient network planning operations, of all types, has become more critical than ever. A common approach to network planning for very large networks has been to partition the nodes into clusters based on communities of interest clusters (“CICs”). In general, CICs are sub-networks of nodes from a larger network. Currently, network planners and engineers partition nodes into CICs based on judgment, experience and intuition. Ideally, network planners and engineers partition CICs so that a good portion of the overall traffic terminates within the same cluster in which it originated. Thus, with CICs, engineers can focus their attention on the smaller individual clusters, instead of having to work with the much larger overall network.
Some existing telecommunications network design procedures cluster nodes based solely on geographic distances. For example, one method defines the “pull” between a pair of nodes to be the inverse of the distance between the nodes, raised to a power. To create p clusters, this method chooses initial root nodes for each cluster, such that the sum of the “pulls” among the p root nodes is minimized. Other nodes are added sequentially to the clusters based on maximizing this “pull” measure.
Another clustering technique is based on a solution to a version of the p-median problem. In a p-median problem, one chooses p median nodes, and each other node is then “assigned” to its nearest median. The objective is to choose medians so that the sum of the distances from each other node to its assigned median is minimized. The nodes assigned to a particular median form a cluster.
Other approaches utilize some sort of “similarity” metric (also called a “proximity” or “nearness” metric) that is based on both distance and demand. For example, one could use the ratio of demand to distance, or the ratio of demand to distance squared, or even a linear combination of a distance-based metric and a demand-based metric. A variety of such approaches in which nodes or groups of nodes are sequentially joined to each other based on values of a similarity metric have been proposed. Another proposal uses similarity-based approaches of this sort within a hierarchical network design procedure. In the context of ring network design, some have proposed “joining” algorithms that start with each node in a separate cluster and then sequentially merge clusters. This proposal uses similarity-based metrics to identify which mergers should be attempted. Since, in the context of ring design, the cost of a cluster corresponds to the cost of a ring, the cost of the solution before and after the proposed merging can be directly computed.
Other existing network design procedures focus primarily on dividing nodes into clusters so as to maximize the amount of intra-cluster demand. To prevent a solution in which all nodes are assigned to a single, large cluster, constraints that somehow restrict the size of any single cluster are needed. One proposal, for example, uses a Tabu Search procedure, which is a known mathematical optimization method, to cluster nodes. In this proposal, the clusters form rings, with constraints on the maximum amount of demand per ring and nodes per ring. Another proposal solves an integer-programming model using decomposition and column generation. Others have proposed a type of exchange heuristic for a related graph-partitioning problem.
Most clustering applications call for non-overlapping clusters such that each node is assigned to a single cluster. Some techniques allow clusters to overlap; however, they assume the objects being clustered can be described by a vector of attributes, rather than as nodes within a particular network structure that exchange demand.